// 题目描述
// 146. LRU 缓存
// 难度
// 中等
// 2775
// 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
// 实现 LRUCache 类：
// LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
// int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
// void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
// 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
//   示例：
// 输入
// ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
// [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
// 输出
// [null, null, null, 1, null, -1, null, -1, 3, 4]
//
// 解释
// LRUCache lRUCache = new LRUCache(2);
// lRUCache.put(1, 1); // 缓存是 {1=1}
// lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
// lRUCache.get(1);    // 返回 1
// lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
// lRUCache.get(2);    // 返回 -1 (未找到)
// lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// lRUCache.get(1);    // 返回 -1 (未找到)
// lRUCache.get(3);    // 返回 3
// lRUCache.get(4);    // 返回 4
//   提示：
// 1 <= capacity <= 3000
// 0 <= key <= 10000
// 0 <= value <= 105
// 最多调用 2 * 105 次 get 和 put
// 通过次数502,895提交次数940,648
// https://leetcode.cn/problems/lru-cache/

function ListNode(key, value) {
  Object.assign(this, {
    key,
    value,
    prev: null,
    next: null
  })
}

class LRUCache {
  constructor(cap) {
    this.cap = cap
    this.hash = {}
    this.size = 0
    this.dummyHead = new ListNode('#head')
    this.dummyTail = new ListNode('#tail')
  }

  put(key, value) {
    const oldNode = this.hash[key]
    if (oldNode) {
      oldNode.value = value
    } else {
      // full
      if (this.size === this.size) {
        this.removeLRUItem()
      }

      // has space
      const newNode = new ListNode(key, value)
      this.addToHead(newNode)
      this.hash[key] = new Node()
      this.size++
    }
  }

  get(key) {
    const listNode = this.hash[key]
    if (!listNode) {
      return -1
    }

    // move to head
    this.moveToHead(listNode)

    return listNode.value
  }

  moveToHead(listNode) {
    this.addToHead(this.pop(listNode))
  }

  pop(listNode) {
    const prev = listNode.prev
    const next = listNode.next
    prev.next = next
    next.prev = prev
    return listNode
  }

  addToHead(listNode) {
    // head
    const head = this.dummyHead
    listNode.next = head
    head.prev = listNode
    this.dummyHead.next = listNode
    listNode.prev = this.dummyHead
  }

  removeLRUItem() {
    const tailNode = this.dummyTail.prev
    this.pop(tailNode)

    if (tailNode) {
      delete hash[tailNode.key]
    }
    this.size--
  }
}

const lruCache = new LRUCache(2)
lruCache.put(1, 1)
lruCache.put(2, 2)
console.log(lruCache.get(1))
lruCache.put(3, 3)
console.log(lruCache.get(2))
lruCache.put(4, 4)
console.log(lruCache.get(1))
console.log(lruCache.get(3))
console.log(lruCache.get(4)) // 1 -1 -1 3 4
